Skip to content
最长连续序列
概述
给定一个未排序的整数数组 nums，找出其中数字连续的最长序列的长度。题目要求算法的时间复杂度为 O(n)，因此基于比较的排序方法（O(n log n)）不能满足要求，需要采用基于哈希集合的线性扫描策略。
基本概念
- 连续序列：若数组中的若干数字经过排序后可以组成一个相差为 1 的连续整数区间（如
[1, 2, 3, 4]），则称这些数字构成一个连续序列。 - 序列起点：在一个连续序列中，只有那些“不存在前驱”的数字才有可能作为序列的起始。对于数字
x，若x - 1不在集合内，则x是一个序列的起点；否则x从属于以x - 1结尾或经过x - 1的序列，无需单独作为起点展开搜索。
工作原理
- 将数组中的所有数字存入一个哈希集合（如
Set），以支持 O(1) 时间复杂度的存在性查询，同时自动去重。 - 遍历集合中的每一个数字
num：- 检查
num - 1是否存在于集合中。若存在，说明num不是某个序列的起点，跳过。 - 若
num - 1不存在，则num是一个序列的起点。从num开始，向后连续检查num + 1,num + 2等是否存在于集合中，每存在一个数字就将当前序列长度加 1，直到中断为止。
- 检查
- 用当前序列长度更新全局最长长度，最终返回该值。
由于每个数字最多只会作为“序列起点检查”被遍历一次，同时又只会作为“序列内部成员”被 while 循环扫描一次，整体时间复杂度为 O(n)。这是一种典型的均摊分析：内层的 while 循环总执行次数受限于数组长度，不存在重复扫描。
基本用法
Node.js
ts
function longestConsecutive(nums: number[]): number {
const numSet = new Set(nums);
let maxLength = 0;
for (const num of numSet) {
// 仅当 num 是序列起点时才启动向后搜索
if (!numSet.has(num - 1)) {
let currentNum = num;
let length = 1;
while (numSet.has(currentNum + 1)) {
currentNum++;
length++;
}
maxLength = Math.max(maxLength, length);
}
}
return maxLength;
}Java
java
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int cur = num;
int len = 1;
while (set.contains(cur + 1)) {
cur++;
len++;
}
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}Python
python
def longestConsecutive(nums: list[int]) -> int:
num_set = set(nums)
max_len = 0
for num in num_set:
if num - 1 not in num_set:
cur = num
length = 1
while cur + 1 in num_set:
cur += 1
length += 1
max_len = max(max_len, length)
return max_len示例
ts
// 示例 1
const nums1 = [100, 4, 200, 1, 3, 2];
console.log(longestConsecutive(nums1)); // 4
// 解释: 最长连续序列是 [1, 2, 3, 4]，长度为 4
// 示例 2
const nums2 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1];
console.log(longestConsecutive(nums2)); // 9
// 解释: 最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]
// 示例 3 (空数组)
const nums3: number[] = [];
console.log(longestConsecutive(nums3)); // 0注意点
- 时间复杂度：外层
for循环遍历集合，内层while循环不会重复扫描同一个数字。每个数字最多被访问两次（一次起点检查，一次作为序列内部元素向后延伸），因此整体时间复杂度为 O(n)。 - 空间复杂度：需要额外使用哈希集合存储所有数字，空间复杂度为 O(n)。
- 去重：哈希集合会自动处理重复元素。数组中重复的数字不会影响序列长度的计算，也不会造成重复扫描。
- 起点判断的必要性：如果没有
num - 1的检查而对每个数字都尝试向后扫描，则最坏情况下时间复杂度会退化为 O(n²)（每个序列成员都会被重复扫描多次）。只从起点启动扫描保证了线性时间。 - 数据范围：算法不依赖元素的具体取值，仅依赖等值判断，因此可以处理任意整数范围，包括负数。
- 排序方案的取舍：排序后再扫描可以得到正确结果，但时间复杂度为
O(n log n)，不符合题目要求的严格 O(n) 约束；同时排序会改变输入顺序，带来额外拷贝或原地修改的开销。
限制
- 算法依赖将所有元素加载到内存中的哈希集合，当数组规模极大且内存受限时可能不适用。
- 哈希集合的平均查询成本是 O(1)，但在极端哈希冲突下单次操作可能退化，不过对于整数类型默认哈希实现通常表现稳定。
- 仅针对整数连续序列设计，无法直接迁移到其他数据类型（例如浮点数连续性或自定义对象的连续属性）上。
- 算法不保留重复元素的频次信息，也不记录序列成员在原数组中的位置索引，若需要这些信息则需另行设计。
应用
这一算法本质上是一种基于哈希的连续区间识别策略，适用于以下场景：
- 寻找无序数据中的最长连续子序列，如用户活跃天数连续登录分析、传感器连续异常时间窗口等。
- 作为流式数据处理的离线校正模块：在允许一定延迟的情况下，使用集合缓存一段窗口内的数据，定期计算最长连续序列。
- 在数据库或缓存层，当需要根据时间戳或序号快速找到最大连续段时，可借鉴该均摊分析的思路，避免对数据进行全排序。